# 436 中等：寻找右区间

def findRightInterval(intervals):
    sortIntervals = sorted(intervals, key=lambda interval: interval[0])
    ret = []
    for interval in intervals:
        # print(interval)
        index = sortIntervals.index(interval)

        # 二分查找
        l, r = index, len(sortIntervals) - 1
        while l <= r:
            mid = l + (r - l) // 2
            if sortIntervals[mid][0] < interval[1]:
                l = mid + 1
            elif sortIntervals[mid][0] > interval[1]:
                r = mid - 1
            else:
                l = mid
                break
        if l >= len(sortIntervals):
            ret.append(-1)
        else:
            ret.append(intervals.index(sortIntervals[l]))

        # j = -1
        # for i in range(index + 1, len(sortIntervals)):
        #     if sortIntervals[i][0] >= interval[1]:
        #         j = i
        #         break
        # if j == -1:
        #     ret.append(-1)
        # else:
        #     ret.append(intervals.index(sortIntervals[j]))
        # print(ret)
    return ret


print(findRightInterval([[3, 4], [2, 3], [1, 2]]))
print(findRightInterval([[4, 5], [2, 3], [1, 2]]))
print(findRightInterval([[1, 4], [2, 3], [3, 4]]))
print(findRightInterval([[1, 4]]))
